package hot_100;

import java.util.Deque;
import java.util.LinkedList;

public class 字符串解码 {
    public static void main(String[] args) {

    }

    public String decodeString(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        Deque<String> deque = new LinkedList<>();
        Deque<Integer> number = new LinkedList<>();
        int num = 0;
        String ans = "";
        for (int i = 0; i < n; i++) {
            if (chars[i] >= '0' && chars[i] <= '9') {
                num = num * 10 + chars[i] - '0';
            } else if (chars[i] == '[') {
                number.addFirst(num);
                num = 0;
                deque.addFirst(ans);
                ans = "";
            } else if (chars[i] == ']') {
                num = number.getFirst();
                number.removeFirst();
                String first = deque.getFirst();
                deque.removeFirst();
                for (int j = 0; j < num; j++) {
                    first += ans;
                }
                deque.addFirst(first);
                ans = first;
                num = 0;
            } else {
                ans = ans + chars[i];
            }
        }
        return ans;
    }


//    public String decodeString(String s) {
//        char[] chars = s.toCharArray();
//        int n = chars.length;
//        Deque<Character> deque = new LinkedList<>();
//        Deque<Integer> number = new LinkedList<>();
//        int num = 0;
//        StringBuilder sb;
//        for (int i = 0; i < n; i++) {
//            if (chars[i] >= '0' && chars[i] <= '9') {
//                num = num * 10 + chars[i] - '0';
//            } else {
//                if (num != 0) {
//                    number.addFirst(num);
//                    num = 0;
//                }
//                if (chars[i] != ']')
//                    deque.addFirst(chars[i]);
//                else {
//                    sb = new StringBuilder();
//                    while (true) {
//                        Character first = deque.getFirst();
//                        deque.removeFirst();
//                        if (first == '[')
//                            break;
//                        sb.append(first);
//                    }
//                    int m = number.getFirst();
//                    number.removeFirst();
//                    char[] chs = sb.reverse().toString().toCharArray();
//                    for (int j = 0; j < m; j++) {
//                        for (char c : chs) {
//                            deque.addFirst(c);
//                        }
//                    }
//                }
//            }
//        }
//        sb = new StringBuilder();
//        while (!deque.isEmpty()) {
//            sb.append(deque.getLast());
//            deque.removeLast();
//        }
//        return sb.toString();
//    }
}
